package com.summli.basic.class06;

import java.util.Stack;

/**
 * 给定一个单链表的头节点head，请判断该链表是否为回文结构。
 */
public class Code02_IsPalindromeList {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    //使用栈结构 时间复杂度O（n）,额外的空间复杂度位O（N）
    public static boolean isPalindrome1(Node head) {
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        Node node1 = head;
        while(!stack.empty()){
            Node node2 = stack.pop();
            if(node1.value != node2.value){
                return false;
            }
            node1 = node1.next;
        }
        return true;
    }

    // 使用stack+链表中点问题 额外的空间复杂度
    public static boolean isPalindrome2(Node head){
        if(head == null){
            return true;
        }
        Node last = head;
        Node fast = head;
        while(fast.next != null && fast.next.next != null){
            last = last.next;
            fast = fast.next.next;
        }
        Stack<Node> stack = new Stack<>();
        while(last.next != null){
            last = last.next;
            stack.push(last);
        }
        Node cur = head;
        while(!stack.empty()){
            if(cur.value != stack.pop().value){
                return false;
            }
            cur = cur.next;
        }
        return true;
    }

    // 使用空间复杂度O（1）
    /*
    你可以找到，中间点（上半点），反转后边的部分，两边开始进行比较，直到出现null
    还原，原来的结构
     */
    public static boolean isPalindrome3(Node head){
        if(head == null){
            return true;
        }
        Node last = head;
        Node fast = head;
        while(fast.next != null && fast.next.next != null){
            last = last.next;
            fast = fast.next.next;
        }
        Node node1 = last.next;
        last.next = null;

        while(node1 != null){
            Node node2 = node1.next;
            node1.next = last;
            last = node1;
            node1 = node2;
        }

        Node leftNode = head;
        Node rightNode = last;
        boolean res = true;
        while(leftNode != null && rightNode != null){
            if(leftNode.value != rightNode.value){
                res = false;
                break;
            }
            leftNode = leftNode.next;
            rightNode = rightNode.next;
        }

        Node nextNode = last.next;
        last.next = null;
        while(nextNode != null){
            rightNode = nextNode.next;
            nextNode.next = last;
            last = nextNode;
            nextNode = rightNode;
        }
        return res;
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        Node head = null;
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(2);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(2);
        head.next.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

    }

}
